/*
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

"0" (0), "1"(1), "abc"(2), "def"(3), "ghi"(4), "jkl"(5), "mno"(6), "pqrs"(7), "tuv"(8), "wxyz"(9)

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
*/

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        int len = digits.size(); 
        if (!len) {
            result.push_back("");
            return result;
        }
        vector<int> num(len, 0);
        do {
            result.push_back(getCombo(digits, num)); 
        } while (getNext(digits, num));
        return result;
    }
private:
    bool getNext(string &digits, vector<int> &num) {
        int i;
        bool rotated = false;
        for (i = 0; i < digits.size(); i++) {
            char c = digits[i];
            int next = num[i];
            if (c != '0' && c != '1') {
                if (c == '7' || c == '9') {
                    next = (next + 1) % 4;
                } else {
                    next = (next + 1) % 3;
                }
            } // else next = next;
            rotated = (next <= num[i]);
            num[i] = next;
            if (!rotated) break;
        }
        return (i < digits.size());
    }
    string getCombo(string &digits, vector<int> &num) {
        static vector<string> lettermap = {
            "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        string str("");
        for (int i = 0; i < digits.size(); i++) {
            int idx = digits[i] - '0';
            str += (lettermap[idx]).at(num[i]);
        }
        return str;
    }
};
